package com.leo.basic.chapter05;

import java.util.Arrays;

/**
 * 分治法复习第一遍
 * @author xuexiaolei
 * @version 2017年12月07日
 */
public class DivideAndConquer001 {
    /**
     * 分治法求最大最小值
     * @param l         数组
     * @param start     起始下标，包含
     * @param end       终点下标，包含
     * @param result    结果数组，第一个表示max，第二个表示min
     */
    public void maxAndMin(int[] l, int start, int end, int[] result){
        if (start == end){
            result[0]=result[1]=l[start];
        }else if (start == end-1){
            result[0] = l[start]>l[end]?l[start]:l[end];
            result[1] = l[start]<l[end]?l[start]:l[end];
        }else {
            int mid = (start+end)/2;
            int[] result1 = new int[2];
            maxAndMin(l, start, mid, result1);
            int[] result2 = new int[2];
            maxAndMin(l, mid+1, end, result2);
            result[0] = result1[0]>result2[0]?result1[0]:result2[0];
            result[1] = result1[1]<result2[1]?result1[1]:result2[1];
        }
    }

    /**
     * 查找有序列表中某个数的位置
     * @param l         数组
     * @param start     起始下标，包含
     * @param end       终点下标，包含
     * @param find      查找的值
     * @return
     */
    public int bSearch(int[] l, int start, int end, int find){
        if (start <= end){
            int mid = (start+end)/2;
            if (l[mid] == find){
                return mid;
            }else if (l[mid] < find){
                return bSearch(l, mid+1, end, find);
            }else{
                return bSearch(l, start, mid-1, find);
            }
        }
        return start;
    }

    public void merge(int[] l, int start, int mid, int end){
        int[] t = new int[end-start+1];
        int i = start, j=mid+1,k=0;
        while (i<=mid && j<=end){
            if (l[i] < l[j]){
                t[k] = l[i];
                i++;
            }else{
                t[k] = l[j];
                j++;
            }
            k++;
        }
        while (i<=mid) t[k++] = l[i++];
        while (j<=end) t[k++] = l[j++];
        for (int m = 0; m < t.length; m++) {
//            l[m] = t[m];//这个错误，写完先自己检查一遍！！！
            l[start+m] = t[m];
        }
    }

    public void mergeSort(int[] l, int start, int end){
        if (start < end){
            int mid = (start+end)/2;
            mergeSort(l, start, mid);
            mergeSort(l, mid+1, end);
            merge(l,start,mid,end);
        }
    }

    /**
     * 重写！！！！！
     * @param l
     * @param start
     * @param end
     * @return
     */
    public static int partition(int[] l, int start, int end){
        int tmp = l[start];
        int i = start,j = end;
        while (i<j){
            while (i<j && l[j]>=tmp) j--;
            l[i] = l[j];
            while (i<j && l[i]<=tmp) i++;
            l[j] = l[i];
        }
        l[i] = tmp;
        return i;
    }
    public static void quickSort(int[] l, int start, int end){
        if (start < end){
            int pos = partition(l, start, end);
            quickSort(l, start, pos-1);
            quickSort(l, pos+1, end);
        }
    }

    /**
     * 竟然用递归写法写出来了！
     * @param l
     * @param start
     * @param end
     * @param k
     * @return
     */
    public static int selectK(int[] l, int start, int end, int k){
        if (start < end){
            int pos = partition(l, start, end);
            if (pos == k-1){
                return l[pos];
            }else if (pos < k-1){
                return selectK(l, pos+1, end, k);
            }else {
                return selectK(l, start, pos-1, k);
            }
        }
        return l[start];
    }

    public static void main(String[] args) {
        int[] a = new int[]{2,6,3,7,27,4,8,2,4,-1,3};
        quickSort(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));

        a = new int[]{2,6,3,7,27,4,8,2,4,-1,3};
        System.out.println(selectK(a,0, a.length-1, 10));
    }

    /**
     * 重写
     * @param l
     * @param start
     * @param end
     * @return
     */
    public static int partition2(int[] l, int start, int end){
        int tmp = l[start];
        int i=start,j=end;
        while (i<j){
            while (i<j && l[j]>=tmp) j--;
            l[i] = l[j];
            while (i<j && l[i]<=tmp) i++;
            l[j] = l[i];
        }
        l[i] = tmp;
        return i;
    }
}
